contain duplicate

Problem Description

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Examples

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

解析

給定一個整數陣列 nums
要求寫一個演算法去判斷是否有重複值

要檢查是否有重複出現的值

最直覺的想法逐步 nums 陣列每個位置的值 來檢查除了自己之外的值是否有重複的值

這樣作法對每個值需要找 len(nums) - 1 個值

所以時間複雜度會是 O(n^2)

然而透過 hashSet 來紀錄每次出現過的值

每次都透過雜湊函數檢查 有沒有出現過 nums[i] 只要花 O(1)

這樣可以讓時間複雜度降低至 O(n)

空間複雜度會變成 O(n) 來紀錄每個走過的值

具體作法如下：

逐次檢查 nums 陣列每個位置的值是否有出現在 hashSet 內

每次只要發現 hashSet 有出現過的值

就直接回傳 true

否則就把值放入 hashSet 來紀錄

如果檢查到最後都沒有找到重複的值代表沒有

時間複雜度為 O(n)
空間複雜度為 O(n)

程式碼

package sol

func containsDuplicate(nums []int) bool {
	hash := make(map[int]struct{})
	for _, val := range nums {
		if _, exist := hash[val]; exist {
			return true
		}
		hash[val] = struct{}{}
	}
	return false
}

困難點

1. 理解 HashTable 作用

Solve Point

• [x] Understand what problem to solve
• [x] Analysis Complexity